Number portability (NP) is a service that allows subscribers to change service providers and/or locations and keep the same telephone number. The term “number portability,” as used herein, is intended to include local number portability (LNP), which refers to porting of landline telephone numbers, and mobile number portability, which refers to porting of mobile telephone numbers. In order to provide number portability service, carriers must maintain a database that translates dialed telephone numbers into exchange identifiers. As the number of subscribers increases, the size of number portability databases will also increase.
ENUM service refers to a service where the E.164-formatted telephone number of a subscriber is translated into one or more uniform resource identifiers (URIs). For example, the telephone number 19194605500 may be translated into 19194605500@tekelec.com. ENUM service allows subscribers to contact Internet protocol (IP) devices, such as IP phones, by dialing an E.164 telephone number. ENUM service requires a database that translates the E.164-formatted number to the corresponding URI(s). Like number portability, as the number of subscribers increases, the size of ENUM databases will also increase.
Current NP and ENUM databases are indexed, in whole or in part, by telephone numbers (TNs). For example, local number portability databases are indexed based on the first six digits of a telephone number, referred to as the numbering plan area code and exchange number (NPA-NXX). If a number within an NPA-NXX range is ported, its entry in the LNP database will contain a location routing number (LRN), which is a ten digit number corresponding to a ported-to end office.
When a ported TN is dialed, the call is routed to the appropriate end office using the LRN associated with the dialed TN. An LRN acts as a pointer to the ported-to end office and can point to switches located in a different geographical area or belonging to a different provider from the donor end office without changing the TN with which the LRN is associated. By maintaining databases containing TNs and any associated LRNs for ported numbers, carriers are able to provide NP service to their customers.
As stated above, NP database size is increasing due to an increased number of subscribers. One drawback of conventional NP databases is that as their size increases, their lookup time and storage requirement increases as well. For example, NP databases in the United States and other countries may now include hundreds of millions of entries. The resulting lookup times delay call setup. In addition, NP databases must be stored in memory, which increases data storage costs. Therefore, a need exists for reducing NP lookup times and storage requirements. Similar problems will occur for ENUM databases as the number of subscribers that require ENUM services increases.
Currently, NP and ENUM databases are separately maintained and accessed, even though some of the data required to access each database type is the same. That is, both ENUM and NP databases have data that can be accessed using a TN. Currently, TN data is duplicated for NP and ENUM data, resulting in wasted storage.
Conventional TN database lookups are typically implemented using binary tree data structures (b-trees). A binary tree data structure is a series of linked nodes wherein each node has at most two dependent nodes, called children. In order to locate an entry in a b-tree data structure, a search key, such as a called party telephone number, is compared with data associated with different branches in the tree. However, a binary tree data structure has several drawbacks.
One drawback associated with binary tree data structures is that as the number of ENUM database entries increases, the number of branches in the tree must also increase, thus increasing the search time as well. Another problem with using b-trees is that sophisticated balancing algorithms are required to ensure that the trees do not become unbalanced. Also, the size of the key in a b-tree structure may be greater than the size of data associated with a key. Another problem associated with b-tree structures is that they cannot be recovered in smaller data blocks since entries in a b-tree relate to each other as branches. Therefore, data recovery requires a reload of the entire database when data is identified as invalid.
In connecting VoIP calls that require ENUM queries, network traffic may be exchanged between administratively distinct networks through the use of peering agreements between the operators of the various networks. Peering agreements are typically contractual arrangements whereby routing information is exchanged between carriers for their mutual benefit. However, complications may arise given the wide variety of peering agreements and network implementations involved. For example, a subscriber on carrier A's network may initiate a voice over Internet protocol (VoIP) call to a subscriber on carrier Z's network. Carrier A may not have a peering agreement directly with carrier Z and thus would not be able to route the calling subscriber's call because it would not have the necessary routing information. However, carrier A may have a peering agreement with carrier B, who may have a peering agreement with carrier C, and so on. In this way, carrier A may be connected using a series of peering agreements, to carrier Z. Since no single carrier has a view of the entire chain, it may not be possible to complete VoIP calls that require multiple peering agreements. Alternatively, each carrier could maintain a copy of all peering agreements between other carriers to select the correct path for the call. However, peering agreements may be proprietary to the carriers involved in each agreement and thus may be unavailable to non-party carriers.
Accordingly, there exists a need for improved methods, systems, and computer program products for providing NP and ENUM services in a telecommunications network.